Problem statement: zenit14ckh

Ondatra Lukáš si robí PhD z architektúry. Pre účely rozhľadu (vedeckého aj vizuálneho) ho jeho školiteľ poslal navštíviť najvyšší mrakodrap na zemi. Lukáš teraz stojí pod mrakodrapom a v úžase pozoruje majestátne sa týčiacu stavbu. Okrem vysokých budov bol vždy fascinovaný výťahmi vo vysokých budovách.

Vnútri mrakodrapu sa nachádza zložitý systém chodieb a výťahov. Lukáš vstúpi do budovy na prízemí a jeho cieľom je dostať sa na najvyššie poschodie. Ak by sa dalo, rád by si vybral čo najdlhšiu súvislú cestu výťahom na toto poschodie.

Na vstupe je prierez mrakodrapom. Ten sa skladá zo stien #, chodieb . a výťahov, ktoré sú označené veľkými písmenami anglickej abecedy. Šachta vyťahu je vždy tvorená rovným stĺpcom písmen. Rôzne šachty, ktoré sa dotýkajú hranou, budeme vždy označovať rôznymi písmenami. Ak sa šachty hranou nedotýkajú, môžeme použiť rovnaké písmeno na označenie dvoch rôznych šácht. Každá šachta je vysoká aspoň dve poschodia. Vstup teda môže vyzerať napríklad takto (čísla naľavo nebudú jeho súčasťou):

8|  #A.E...C#
7|  #A#E#..C.
6|  #A.ED.#C.
5|  #A##DB#C.
4|  #A.#DB#C#
3|  ###C#B#C.
2|  ###C.B#C.
1|  #F.C.B.##
0|  .F...B...

Ak Lukášovi nestojí v ceste stena, môže sa pohybovať v rámci poschodia horizontálne. Ak má k dispozícii výťah, môže zmeniť poschodie na ľubovoľné (smerom hore aj dole), ktoré je v dosahu príslušného výťahu. Výťahová šachta je v rámci poschodia priechodná ako chodba. Napríklad teda môžeme na prvom poschodí vystúpiť z výťahu F, prejsť okolo výťahu C a nastúpiť do výťahu B.

Lukáš môže použiť ľubovoľne veľa výťahov a tiež môže použiť jeden výťah viackrát (aj rôznymi smermi). Jeho primárnym cieľom je dostať sa na najvyššie poschodie. Akonáhle sa tam prvýkrát dostane, už nerobí žiadne ďalšie presuny. V príklade vyššie teda nemôže prísť hore výťahom A a nasadnúť do výťahu C. Jeho sekundárnym cieľom je maximalizovať výšku prekonanú poslednou jazdou výťahom.

V príklade vyššie je jedna z optimálnych možností nasledovná: pomocou výťahov B a D sa najprv dostať k výťahu A. Všimnite si, že je potrebné použiť výťah D, pretože na štvrtom poschodí je medzi šachtou B a A stena. Výťahom A najprv Lukáš zíde o dve poschodia nižšie, aby sa potom mohol súvislo odviezť 4 poschodia na vrchol. O dlhom výťahu C môžeme len snívať: nevieme sa k nemu dostať ináč ako cez najvyššie poschodie a to máme v tejto úlohe zakázané.

Vstup a výstup

Na prvom riadku vstupu je výška a šírka prierezu mrakodrapu. Tieto čísla sú aspoň 2 a najviac 100. Mrakodrap spĺňa popis vyššie. Môžete predpokladať, že najnižšie poschodie neobsahuje steny. Na výstup vypíšte najvyššiu dosiahnuteľnú výšku v poschodiach, ktorú Lukáš dokáže prekonať posledným výťahom, ktorý použije (teda tým, ktorým príde na najvyššie poschodie). V prípade, že neexistuje žiadna cesta na najvyššie poschodie, vypíšte NEDA SA.

Príklady

Input:

9 9
#A.E...C#
#A#E#..C.
#A.ED.#C.
#A##DB#C.
#A.#DB#C#
###C#B#C.
###C.B#C.
#F.C.B.##
.F...B...

Output:

4

Input:

8 11
######K#X##
G.....K#X##
G...B#K#X..
G###B#K.X..
G...B.##X#D
G.##B###X#D
..A#B.C#X#D
..A.B.C...D

Output:

6

Lukáš sa môže dostať k výťahu X postupne použitím výťahov B, G a K.

Input:

2 2
..
..

Output:

NEDA SA